/**
 * 计数排序
 * 数据量小则可以开辟数组用于计数
 *
 * 优点：时间复杂度较低，平均为：O(n + k)
 * 缺点：输入的数据必须是有确定范围的整数，即给定了数据范围
 *
 * 实现思路：
 * 若给定数据范围：-50000 <= nums[i] <= 50000
 * 则开辟 2 * 50000 + 1 空间的数组，用于记录元素出现的次数
 * counts[100001] = 5，说明 nums 中元素 50000 出现了 5 次
 * counts[0] = 3，说明 nums 中元素 -50000 出现了 3 次
 */
public class CountingSort {
    public static int[] countingSort(int[] nums) {
        int len = nums.length;
        int[] counts = new int[2 * 50000 + 1];
        for (int num : nums) {
            counts[num + 50000] ++;
        }

        int[] res = new int[len];
        int idx = 0;
        for (int i = 0; i < counts.length; i++) {
            while (counts[i] > 0) {
                // 往 res 中依次放入元素
                res[idx ++] = i - 50000;
                counts[i] --;
            }
        }
        return res;
    }
}
